#coding:utf-8

from myqueue import Queue

class BinaryTree(object):
    """二叉树"""
    def __init__(self,item = None) -> None:
        self.node = item
        self.lchild = None
        self.rchild = None
    def add(self, item):
        """广度优先添加叶子"""
        if self.node is None:
            self.node = item
            return
        node = BinaryTree(item)
        que = Queue(self)
        while not que.is_empty():
            cur_node = que.dequeue()

            if cur_node.lchild is None:
                cur_node.lchild = node
                return
            else:
                que.enqueue(cur_node.lchild)
            if cur_node.rchild is None:
                cur_node.rchild = node
                return
            else:
                que.enqueue(cur_node.rchild)

    def breath_travel(self):
        """按照广度优先顺序遍历"""
        if self.node is None:
            print("这是空树")
            return
        que = Queue(self.node)
        while not que.is_empty():
            cur_node = que.dequeue()
            print(cur_node.node)        # 打印出节点
            if cur_node.lchild is not None:
                que.enqueue(cur_node.lchild)
            if cur_node.rchild is not None:
                que.enqueue(cur_node.rchild)     

    def action(self,node):
        """遍历时执行的操作"""
        print(node.node,end=' ')
    #    print('#',end=" ")

    def __preorder(self,node,action):
        if node is None:return
        action(node)
        self.__preorder(node.lchild,action)   
        self.__preorder(node.rchild,action) 

    def __inorder(self,node,action):
        if node is None:return
        self.__inorder(node.lchild,action)  
        action(node)
        self.__inorder(node.rchild,action)         

    def __postorder (self,node,action):
        if node is None:return
        self.__postorder(node.lchild,action)  
        self.__postorder(node.rchild,action)
        action(node) 

    def preorder(self,action):
        """先序遍历"""
        self.__preorder(self,action)

    def inorder(self,action):
        """中根遍历"""
        self.__inorder(self,action)

    def postorder (self,action):
        """后根遍历"""    
        self.__postorder(self,action)


if __name__ == "__main__":
    b = BinaryTree()
    b.add('0')
    b.add('1')
    b.add('2')
    b.add('3')
    b.add('4')
    b.add('5')
    b.add('6')
    b.add('7')
    b.add('8')
    b.add('9')
#    b.breath_travel()
    print("先根：")
    b.preorder(b.action)
    print("\r\n中根：")    
    b.inorder(b.action)
    print("\r\n后根")    
    b.postorder(b.action)
    print("\r\nend")    

